/* 查找单链表中倒数第k个结点，若成功，则输出该节点的 data，并返回 1，否则返回。*/
#include <iostream>
#include "headfun.h"
using namespace std;

// 法一标准解
int find(LNode *head, int k)
{
  // 让q和p相距 k 个结点
  LNode *q = head->next;
  LNode *p = head;
  
  // 记录q指向的结点索引
  int i = 1;
  
  // 遍历链表
  while (q != NULL)
  {
    q = q->next;
    ++i;
    
    // 当相距k个结点时，开始同时移动p
    if (i > k)
      p = p->next;
  }
  
  // 如果没有移动p，则不存在倒数第k个结点
  if (p == head)
    return 0;
  
  // 否则，打印数值
  else
  {
    cout << "倒数第K个节点为：" << p->data;
    return 1;
  }
}

// 法二暴力解

// 返回链表长度
int len(LNode *L)
{
  LNode *p = L->next;
  int n = 0;
  while (p != NULL)
  {
    p = p->next;
    ++n;
  }
  return n;
}

// 找到倒数第k个结点
int Find(LNode *L, int k)
{
  int i = 0, m;
  
  // 根据链表长度，计算指针要移动多少次
  m = len(L) - k + 1;
  
  // 没有倒数第k个结点
  if (m <= 0)
  {
    return 0;
  }
  
  // 移动指针
  while (i < m)
  {
    L = L->next;
    ++i;
  }
  
  // 返回数值
  cout << L->data;
  return 1;
}

int main()
{
  // 创建链表
  LNode *L = head_Linklist();
  
  // 寻找倒数第三个结点
  int j = find(L, 3);
}
